package acwing_04;

import java.util.Scanner;

public class _868_筛质数 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		boolean arr[] = new boolean[n+1];
		// 朴素筛法：将质数的倍数的值设置为true，说明其不是质数，最终剩下为false的值就是质数
		// 优化：
		// 如果一个数不是质数，那么能整除它的数实际是成对出现的，比如16能被2 4 6 8整除
		// 同时，如果一个数不是质数，那么能最小的整除的数会<=num/i也就是sqrt(num)
		// 那么我们只需要找出<=n/i的质数，对它们不断倍增，倍增的数就包含了后面非质数的值，能被质数倍增得到的值说明该值不是质数
		for(int i = 2; i <= n / i; i++) {
			if(!arr[i]) {
				for(int j = i+i; j <= n; j+=i) {
					arr[j] = true;
				}
			}
		}
		int count = 0;
		
		for(int i = 2; i <= n; i++) {
			if(!arr[i]) {
				count++;
			}
		}
		
		System.out.println(count);
		scan.close();
		
	}
}
